package simple;

import data.ListNode;

import java.util.ArrayList;
import java.util.List;

/**
 * @author cmqzyd0700@163.com
 * @version 1.0
 * @since 2020/7/28 20:44
 */
public class No206_反转链表 {
    public static void main(String[] args) {
        Solution206 solution206 = new Solution206();
        ListNode listNode = new ListNode(1);
        listNode.add(2);
        listNode.add(3);
        listNode.add(4);
        ListNode listNode1 = solution206.reverseList(listNode);
        System.out.println(listNode1);
    }
}

class Solution206 {
    public ListNode reverseList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        //递归法,充分利用值传递
        ListNode save = reverseList(head.next);
        head.next.next = head;
        head.next = null;
        return save;
    }
}



    //public ListNode reverseList(ListNode head) {
    //    //1->2->3->4
    //    //1. list  (1,2,3,4)
    //    //2. addList(ListNode head,int data):
    //    //3. 倒序遍历 (4,3,2,1)  4->3->2->1
    //    //暴力额外空间
    //
    //    //存放head遍历之后的数据
    //    List<Integer> list = new ArrayList<>();
    //    while (head != null) {
    //        int data = head.val;
    //        list.add(data);
    //        head = head.next;
    //    }
    //
    //    ListNode res = new ListNode(-1);
    //
    //    //倒序遍历
    //    for (int i = list.size() - 1; i >= 0; i--) {
    //        int resData = list.get(i);
    //        //倒序元素加链表
    //        addList(res, resData); //-1->4->3->2->1
    //    }
    //    return res.next;
    //}
    //
    ////将data加入head的尾部
    //public void addList(ListNode head, int data) {
    //    //头法,模板,保存头,刷回去
    //
    //    //保存头
    //    ListNode headCp = head;
    //    //模板
    //    while (head != null && head.next != null) {
    //        head = head.next;
    //    }
    //    head.next = new ListNode(data);
    //
    //    //刷回去
    //    head = headCp;
    //}



    //public ListNode reverseList(ListNode head) {
    //    //三指针
    //    ListNode red = null;
    //    ListNode green = head;
    //    while (green != null) {
    //        ListNode yellow = green.next;
    //        green.next = red;
    //        red = green;
    //        green = yellow;
    //    }
    //    return red;
    //}
